package cn.dduan.fool.collection.map;

import java.util.HashMap;
import java.util.concurrent.ConcurrentHashMap;

/**
 * HashMap
 * <p>
 * Map接口基于哈希表的实现，是使用频率最高的用于键值对处理的数据类型。
 * 它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，特点是访问速度快，遍历顺序不确定，线程不安全，最多允许一个key为null，允许多个value为null。
 * 可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap类
 * <p>
 * 特点：
 * 1、数据结构：1.7【数组 + 链表】、1.8【数组 + 链表/红黑树】
 * 2、是否线程安全：否
 * 3、key是否可为null：是
 * 4、是否有序：否
 * <p>
 * 注意：
 * 1、JDK 1.8 引入了红黑树
 * 2、当链表的长度大于 8 的时候就会转换为红黑树，不过，在转换之前，会先去查看 table 数组的长度是否大于 64，如果数组的长度小于 64，那么 HashMap 会优先选择对数组进行扩容 resize，而不是把链表转换成红黑树
 * 3、JDK 1.7采用的是头插法，JDK 1.8 改成了尾插法，因为 JDK 1.7 中采用的头插法在多线程环境下可能会造成循环链表问题
 * <p>
 * 扩容因素：
 * 1、存入数据长度 > 最大容量/长度（Capacity） * 负载因子（LoadFactor）时，进行扩容
 * <p>
 * 扩容分为两步：
 * 1、扩容：创建一个新的 Entry/Node 空数组，长度是原数组的 2 倍
 * 2、ReHash：遍历原 Entry/Node 数组，把所有的 Entry/Node 节点重新 Hash 到新数组
 *
 * @author dduan
 * @version 1.0
 * @date 2023/3/28
 */
public class MyHashMap {
    public static void main(String[] args) {
        // MyHashMap.testThreadSafe();
        MyHashMap.circularList();
    }

    /**
     * HashMap 循环链表问题
     *
     * @author dduan
     * @version 1.0
     * @date 2025/3/10
     */
    private static void circularList() {
        final HashMap<Integer, Object> map = new HashMap<>(20000);

        // 测试线程安全
        Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 10000; i++) {
                    map.put(i, "A" + i);
                }
            }
        });
        t1.start();

        Thread t2 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 10000; i++) {
                    map.put(i, "B" + i);
                }
            }
        });
        t2.start();

        // 等待t1、t2线程执行完成
        try {
            t1.join();
            t2.join();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }

        System.out.println("map size: " + map.size());
    }

    /**
     * test线程安全
     *
     * @author dduan
     * @version 1.0
     * @date 2025/3/10
     */
    private static void testThreadSafe() {
        HashMap<Integer, Integer> hashMap1 = new HashMap<>();
        ConcurrentHashMap<Integer, Integer> hashMap = new ConcurrentHashMap<>();
        // Map<Integer, Integer> hashMap = Collections.synchronizedMap(hashMap1);

        // 测试线程安全
        Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 1000; i++) {
                    hashMap.put(i, i);
                    System.out.println("add key = " + i);
                }
            }
        });
        t1.start();

        Thread t2 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 1000; i++) {
                    hashMap.remove(i);
                    System.out.println("remove key = " + i);
                }
            }
        });
        t2.start();

        // 等待t1、t2线程执行完成
        try {
            t1.join();
            t2.join();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }

        System.out.println(hashMap.toString());
    }
}
